package leetcode.剑指offer.后40;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/1 22:42
 * @description：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/
 */
public class 剑指_57_和为s的两个数字 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    //二分 + 遍历
    /*
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                int tar = target - num;
                int l = 0;
                int r = nums.length - 1;
                if (tar < num) {
                    r = i;
                } else l = i;
                if (binary_search(nums, tar, l, r) != -1) {
                    return new int[]{num, tar};
                }
            }
            return null;
        }

        private int binary_search(int[] nums, int tar, int l, int r) {
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= tar) {
                    l = mid;
                } else
                    r = mid - 1;
            }
            return nums[l] == tar ? l : -1;
        }
    }
     */


    class Solution {
        public int[] twoSum(int[] nums, int target) {
            int i = 0, j = nums.length - 1;
            while (i < j) {
                int s = nums[i] + nums[j];
                if (s < target) i++;
                else if (s > target) j--;
                else return new int[]{nums[i], nums[j]};
            }
            return new int[0];
        }
    }
}
